/*
    libnbds
    Non-blocking Data Structures Library

    Copyright (C) 2011 Paweł Dziepak

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef NBDS_LIST_H
#define NBDS_LIST_H

#include "type.h"

namespace nbds {
	class list_base {
	protected:
		struct elem {
			void *obj;
			elem *next;
			elem *prev;
		};

		class iterator_base {
		private:
			elem *head;
			elem *tail;
			elem *null_element;

			bool cycle;

		protected:
			elem *current;

		public:
			iterator_base(elem*, elem*, elem*, elem*);
			iterator_base(elem*, elem*, elem*);

			iterator_base(const iterator_base&);
			iterator_base &operator=(const iterator_base&);

			iterator_base &operator++();
			iterator_base &operator--();

			bool at_end();
			bool at_begin();
			bool did_cycle();
		};

		elem *head;
		elem *tail;
		elem *null_element;

		list_base();
		~list_base();

		void push_back_(void *);
		void push_front_(void *);

		bool is_empty_();		
	};

	template<typename T, bool is_primitive>
	class list_wrapper { };

	template<typename T>
	class list_wrapper<T, false> : public list_base {
	public:
		class iterator : public iterator_base {
		public:
			iterator(elem *c, elem *h, elem *t, elem *n) :
				iterator_base(c, h, t, n) { }

			iterator(elem *h, elem *t, elem *n) :
				iterator_base(h, t, n) { }

			iterator(const iterator_base &x) :
				iterator_base(x) { }

			iterator &operator=(const iterator &x) {
				iterator_base::operator=(x);

				return *this;
			}

			T &operator*() {
				return *reinterpret_cast<T*>(current->obj);
			}

			T *operator->() {
				return reinterpret_cast<T*>(current->obj);
			}

			iterator &operator++() {
				iterator_base::operator++();

				return *this;
			}

			iterator operator++(int) {
				iterator it = *this;
				iterator_base::operator++();
				return it;
			}

			iterator &operator--() {
				iterator_base::operator--();

				return *this;
			}

			iterator operator--(int) {
				iterator it = *this;
				iterator_base::operator--();
				return it;
			}
		};

		void push_back(const T &obj) {
			T *x = new T(obj);
			push_back_(reinterpret_cast<void*>(x));
		}

		void push_front(const T &obj) {
			T *x = new T(obj);
			push_front_(reinterpret_cast<void*>(x));
		}

		iterator begin() {
			return iterator(head, tail, null_element);
		}

		iterator end() {
			return iterator(tail, head, tail, null_element);
		}

		bool is_empty() {
			return is_empty_();
		}
	};

	template<typename T>
	class list_wrapper<T, true> : public list_base {
	public:
		class iterator : public iterator_base {
		public:
			iterator(elem *c, elem *h, elem *t, elem *n) :
				iterator_base(c, h, t, n) { }

			iterator(elem *h, elem *t, elem *n) :
				iterator_base(h, t, n) { }

			iterator(const iterator_base &x) :
				iterator_base(x) { }

			iterator &operator=(const iterator &x) {
				iterator_base::operator=(x);

				return *this;
			}

			T &operator*() {
				return *reinterpret_cast<T*>(&current->obj);
			}

			T *operator->() {
				return reinterpret_cast<T*>(&current->obj);
			}

			iterator &operator++() {
				iterator_base::operator++();

				return *this;
			}

			iterator operator++(int) {
				iterator it = *this;
				iterator_base::operator++();
				return it;
			}

			iterator &operator--() {
				iterator_base::operator--();

				return *this;
			}

			iterator operator--(int) {
				iterator it = *this;
				iterator_base::operator--();
				return it;
			}
		};

		void push_back(const T &obj) {
			push_back_(reinterpret_cast<void*>(obj));
		}

		void push_front(const T &obj) {
			push_front_(reinterpret_cast<void*>(obj));
		}

		iterator begin() {
			return iterator(head, tail, null_element);
		}

		iterator end() {
			return iterator(tail, head, tail, null_element);
		}

		bool is_empty() {
			return is_empty_();
		}
	};

	template<typename T>
	class list : public list_wrapper<T, is_primitive<T>::value> { };
}

#endif
